// 下标从1开始
// 第一个参数是传入数组的类型
// 第二个参数是所需统计的和的类型
template<class T, class ST = T>
struct Differ2D {
	Differ2D(const vector<vector<T>> &v) {
		int n = v.size(), m = v[0].size();
		diff_.resize(n + 2);
		for (int i = 0; i <= n + 1; i++) {
			diff_[i].resize(m + 2, 0);
		}
		for (int i = 1; i < n; i++) {
			for (int j = 1; j < m; j++) {
				modify(i, j, i, j, v[i][j]);
			}
		}
	}

	void modify(const int x1, const int y1, const int x2, const int y2, const int c) {
		diff_[x1][y1] += c;
		diff_[x2 + 1][y1] -= c;
		diff_[x1][y2 + 1] -= c;
		diff_[x2 + 1][y2 + 1] += c;
	}

	vector<vector<ST>> recover() {
		int n = diff_.size() - 1, m = diff_[0].size() - 1;
		for (int i = 1; i < n; i++) {
			for (int j = 1; j < m; j++) {
				diff_[i][j] += diff_[i - 1][j] + diff_[i][j - 1] - diff_[i - 1][j - 1];
			}
		}
		return diff_;
	}
	vector<vector<ST>> diff_;
};
int main() {
	vector<vector<int>> s(4, vector<int>(4, 0));
	for (int i = 1;i <= 3; i++) {
		for (int j = 1; j <= 3; j++) {
			s[i][j] = i * 3 + j;
			cout << s[i][j] << ' ';
		}
		cout << '\n';
	}
	Differ2D<int, int> st(s);
	st.modify(1, 1, 2, 2, 2);
	st.modify(1, 1, 3, 3, 2);
	auto result = st.recover();
	for (int i = 1; i <= 3; i++) {
		for (int j = 1; j <= 3; j++) {
			cout << result[i][j] << ' ';
		}
		cout << endl;
	}
	return 0;
}